package com.mashibing.class02;

import javax.lang.model.element.VariableElement;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 题目五:
 *一个数组中有一种数出现K次, 其他数都出现了M次,
 * M > 1, K < M
 * 找到, 出现了K次的数,
 * 要求, 额外空间复杂度O(1), 时间复杂度O(N)
 */
public class Code08_KM {

    public static int test(int[] arr,int k, int m){
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : arr) {
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }
        for (Integer num : map.keySet()) {
            if (map.get(num)==k){
                return num;
            }
        }
        return -1;
    }

    // 请保证arr中, 只有一种数出现了K次, 其他的数都出现了M次
    public static int onlyKTimes(int[] arr, int k, int m){
        int[] t = new int[32]; // 词频统计变量
        // t[0] 0位置的1出现了几个
        // t[1] 1位置的1 出现了几个
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                t[i] += (num>>i)&1;
//                if (((num>>i)&1)!=0){
//                    t[i]++;
//                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (t[i]%m!=0 ){ // 数字在第i位上, 有 1.
                ans |= (1<<i);
            }
        }
        return ans;
    }

    public static int[] randomArray(int maxKinds,int range,int k,int m){

        int ktimeNum = randomNumber(range); //(int) (Math.random()*range);
        int numKinds = (int) (Math.random()*maxKinds) + 2;
        // k*1+(numKinds - 1)*m
        int[] arr = new int[k + (numKinds - 1) * m];
        int index = 0;
        for (;index<k;index++){
            arr[index] = ktimeNum;
        }
        numKinds--;
        HashSet<Integer> set = new HashSet<Integer>();
        set.add(ktimeNum);
        while (numKinds!=0){
            int curNum = 0;
            do {
                curNum = randomNumber(range);
            }while (set.contains(curNum));
            set.add(curNum);
            numKinds--;
            for(int i = 0; i<m; i++){
                arr[index++] = curNum;
            }
        }
        // arr 填好了
        for (int i = 0; i < arr.length; i++) {
            // i 位置的数 我想随机和j位置的说做交换
            int j = (int) (Math.random()*arr.length);
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        return arr;
    }

    //[-range,range]
    public static int randomNumber(int range){
        return (int) (Math.random()*range) +1;
    }

    public static void main(String[] args) {
//       int[] arr = {4,3,1,3,3,1,1,4,5,5};
//       int k = 2;
//       int m = 3;
//       System.out.println(onlyKTimes(arr,k,m));
       int kinds = 4;
       int range = 200;
       int testTime = 10000;
       int max = 9;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            //(int)(Math.random()*max) 0 ~ 8
            int a = (int)(Math.random()*max)+ 1;// 1 ~ 9
            int b = (int)(Math.random()*max)+ 1;// 1 ~ 9
            int k = Math.min(a,b);
            int m = Math.max(a,b);
            // k<m
            if (k==m){
                m++;
            }
            int[] arr = randomArray(kinds,range,k,m);
            int ans1 = test(arr,k,m);
            int ans2 = onlyKTimes(arr,k,m);
            if (ans1!=ans2){
                System.out.println("出错了!");
            }
        }
        System.out.println("测试结束");
    }
}
